package binaryTree;

class Class1008 {
    public TreeNode bstFromPreorder(int[] preorder) {
        if (preorder.length==0){
            return  null;
        }
        return  build(preorder,0, preorder.length-1);
    }

    public TreeNode  build(int [] preorder,int lo,int hi){
        if (lo>hi){
            return  null;
        }
        if (lo==hi){
            return new TreeNode(preorder[lo]);
        }
        int rootVal=preorder[lo];
        int rightValIndex=lo+1;
//        for (int i = lo+1; i <=hi ; i++) {
//            if (preorder[i]>rootVal){
//                rightValIndex=i;
//                break;
//            }
//        }
        while (rightValIndex<=hi){
            if (preorder[rightValIndex]>preorder[lo]){
                break;
            }
            rightValIndex++;
        }


        TreeNode root = new TreeNode(rootVal);
        root.left=build(preorder,lo+1,rightValIndex-1);
        root.right=build(preorder,rightValIndex,hi);
        return  root;
    }

    public static void main(String[] args) {
        Class1008 class1008 = new Class1008();
        class1008.bstFromPreorder(  new int[]{4,2});
    }


}
